package com.zrkizzy.linkedlist;

import java.util.HashMap;
import java.util.Map;

/**
 * 160. 相交链表<br/>
 *
 * @author zhangrongkang
 * @since 2022/11/17
 * @see <a href="https://leetcode.cn/problems/intersection-of-two-linked-lists/description/">...</a>
 */
public class 相交链表 {
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    class Solution01 {
        // 双指针
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            // 特殊情况
            if (headA == headB) {
                return headA;
            }
            // 定义两个节点
            ListNode link1 = headA, link2 = headB;

            while (link1 != link2) {
                // 短链表先遍历完后继续遍历长链表
                // 如果当前链表遍历完成后继续跳到另一条链表
                link1 = link1 == null ? headB : link1.next;
                link2 = link2 == null ? headA : link2.next;

                // 如果当前链表找到了第一个公共节点则直接返回
                if (link1 == link2) {
                    return link1;
                }
            }

            // 如果能够找到相交的节点则将节点进行返回
            return null;
        }
    }

    class Solution02 {
        // 哈希表
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            // 定义用于存储节点的哈希表
            Map<ListNode, Integer> map = new HashMap<>();
            // 先遍历第一个链表，并将所有节点都添加到哈希表中
            while (headA != null) {
                map.put(headA, 0);
                headA = headA.next;
            }

            // 遍历第二个链表
            while (headB != null) {
                // 判断哈希表中是否存储过当前节点
                if (map.containsKey(headB)) {
                    return headB;
                }
                headB = headB.next;
            }
            // 代码执行到这里说明没有相交的节点
            return null;
        }
    }
}
